#include <iostream>
#include <fstream>
#include "linkStack.h"
#include "linkQueue.h"
#include "binaryTree.h"
using namespace std;
template <typename T>
void creatbyQueue(LinkQueue<T>& q, binaryTree<T>* t);
template <typename T>
void input(LinkQueue<T>& q);
template <typename T>
void output(binaryTree<T>* t);
int main() {
	LinkQueue<char> q;
	binaryTree<char>* t = new binaryTree<char>;
	input(q);
	q.OutPut(cout);
	cout << '\n';
	creatbyQueue(q, t);
	cout << '\n';
	output(t);
	return 0;
}
template <typename T>
void input(LinkQueue<T>& q){
	LinkStack<char> s;
	char ch;
	char temp;
	ifstream read;
	read.open("e://input.txt");
	while (read.get(ch)) {
		temp = 0;
		if (ch >= 'a' && ch <= 'z')
			q.Insert(ch);
		else if (s.IsEmpty())
			s.Push(ch);
		else {
			if (ch == '(')
				s.Push(ch);
			else if (ch == ')') {
				do {
					s.Pop(temp);
					if(temp!='(')q.Insert(temp);
				} while (temp != '(');
			}
			else if (ch == '*' || ch == '/') {
				do {
					if (!s.Pop(temp)) break;
					if(temp!='+'&&temp!='-'&&temp!='(')q.Insert(temp);
				} while (temp != '+' && temp != '-' && temp != '(');
				if (temp == '+'|| temp == '-' || temp == '(')
					s.Push(temp);
				s.Push(ch);
			}
			else if (ch == '+' || ch == '-') {
				do {
					if (!s.Pop(temp)) break;
					if(temp!='(')q.Insert(temp);
				} while (temp != '(');
				if (temp == '(')
					s.Push(temp);
				s.Push(ch);
			}
		}
	}
	while (s.Pop(temp))
		q.Insert(temp);
	read.close();
}
template <typename T>
void creatbyQueue(LinkQueue<T>& q, binaryTree<T>* t) {
	LinkStack<Node<T>*> s;
	T x;
	Node<T>* sx;
	Node<T>* sy;
	Node<T>* temp1;
	Node<T>* temp2 = nullptr;
	while (q.Delete(x)) {
		temp1 = new Node<T>(x);
		if (x >= 'a' && x <= 'z')
			s.Push(temp1);
		else {
			s.Pop(sy);
			s.Pop(sx);
			temp2 = new Node<T>(x, sx, sy);
			s.Push(temp2);
		}
	}
	t->setRoot(temp2);
}
template <typename T>
void output(binaryTree<T>* t){
	ofstream out;
	int depth= 0;
	out.open("e://output.txt");
	t->inverseTraverse(t->getRoot(),out,depth);
	out.close();
}